In digital communications systems, data is routinely transmitted between many processing devices over a network. For example, in computer networks such as the Internet, data is typically sent from one computer to another through network communications devices such as modems, hubs, routers, bridges, switches and/or other computers interconnected by transmission media or data links. The data itself is stored and communicated as a series of binary digits (bits) represented by zeros and ones. During data communications, the manner in which the bits of data are specifically arranged and the order in which they are exchanged between devices is called a protocol. Protocols are usually established by industry standards. There are many different types of protocols serving different purposes, but each typically involves a sending device that arranges data in one manner, and a receiving device that detects the specific arrangement of the data in order to make use of the data upon reception.
For example, blocks of data can be reduced in size by compression protocols before transmission from a sending computer in order to conserve bandwidth. When privacy is desired, data can be altered by encryption protocols into a state that makes the data unreadable by anyone or any device not authorized to read the data. The data can travel across the network in an encrypted and compressed state until it reaches its destination. Upon receipt, the receiving computer decrypts (i.e. decodes) and decompresses the data according to these protocols into a form useable by an intended application.
In some data communications devices, the main central processing unit (CPU) of the device is responsible for performing protocols on data, such as the compression, decompression and encryption, decryption protocols noted above. In this case, the protocols are performed completely under software control by a program stored in memory. In other devices, separate dedicated hardware processors are provided to perform individual protocols. In hardware implementations, the CPU of the device merely schedules the flow of data through the device, and at the appropriate time, instructs each separate dedicated processor to perform a single respective protocol for which that dedicated processor is designed.
For instance, in a modem, as data is received from the sending application it is buffered in memory before transmission onto a computer network. The CPU in the modem assembles the data into a packet, and then compresses that packet of data. After compression, if privacy is desired, the CPU then encrypts the data packet. When the CPU has completed its task, the packet is processed further and transmitted from the modem.
An example of one type of compression/decompression protocol is called V.42bis. To compress data, V.42bis creates a dictionary of commonly occurring strings of bits in data. For a string that commonly occurs, the dictionary specifies a short replacement string which, when transmitted, takes up less space, and therefore saves network bandwidth. Compressed data according to V.42bis is stored in a data structure called a "trie". Tries are a species of multi-way search trees, designed to represent sets of character strings. To decompress data stored in a trie, a complex series of trie traversals are required to reconstruct the original data. Prior art systems perform these trie traversals in either software or with a dedicated hardware processor, as explained above.
Other protocols exist that are used to format data during data communications in order for devices to communicate effectively and efficiently. For instance, during assembly of data packets, signaling information must be provided along with the actual message data in the packets for communications to take place. Various signaling protocols have been developed to support uniform communication of data packets.
One such widely used protocol is the High Level Data Link Control ("HDLC") protocol, as defined in Level 2 of the Open Systems Interconnection ("OSI") model. HDLC is a bit-oriented protocol for sending packets between devices. HDLC requires the sender to distinguish the start and end of a packet from the actual data portion of the packet. To do so, HDLC uses a flag to indicate the start and end of packets. The flag consists of a zero bit followed by six one bits and ends with a zero bit, and appears as 01111110. In HDLC, a process called "zero stuffing" can be used to distinguish the flag portion of a packet from the data portion (which may itself contain an embedded series of ones that could be mistaken for a flag). In zero stuffing, a zero bit "0" is inserted into packet data being transmitted if five continuous one bits "11111" are detected. Thus, zero stuffing converts "11111" into "111110" in the data portion of a packet, in order to distinguish the data from the beginning and end of the packet. The receiver of the "stuffed" data packet then "unstuffs" the data by removing any zero bit following five continuous one bits (i.e., 111110 becomes 11111).
Other protocols called SLIP ("Serial Line Internet Protocol") and PPP ("Point-To-Point") are communications protocols that allow computers to simulate a direct connection to the Internet. SLIP/PPP uses special control characters that need to be detected and/or replaced in the data stream. Creation and insertion as well as detection and replacement of the control characters in prior art SLIP/PPP protocol systems is typically done with a dedicated hardware circuit processing each packet transmitted and received.
Another process occurring in data communications is called the Cyclic Redundancy Check ("CRC"). CRC is the most common method of error detection for most data communications. A CRC value is computed for a packet, attached to that packet during transmission, and upon receipt of that packet the receiver can verify the correctness of the contents of the packet by re-calculating the CRC value using the packet data and comparing the result to the attached CRC. As with the aforementioned protocols, prior art CRC computation is performed either in dedicated hardware circuitry or in software using the CPU of the device.